package algorthm.systemTraning.mergeSort.countRange;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * @className: CountRange
 * @Description:
 * @Author: wangyifei
 * @Date: 2022/9/26 14:02
 */
public class CountRange {
    private static Logger logger = LoggerFactory.getLogger(CountRange.class);
    public static int countRange(int[] array , int l , int r){
        if(null == array || array.length == 0){
            return -1 ;
        }
        if(null != array && array.length == 1){
            if(array[0] >= l && array[0] <= r){
                return 1 ;
            }
        }

        int[] preSum = new int[array.length];
        int sum = 0 ;
        for(int i = 0 ; i < array.length ; i++){
            preSum[i] = sum + array[i];
            sum = preSum[i];
        }
        return process(preSum , l , r , 0 , array.length - 1);
    }
    public static int process(int[] preSum , int l , int r , int start , int end){
        if(start == end){
            if(preSum[start] >= l && preSum[start] <= r){
                return 1 ;
            }
            return 0 ;
        }
        int mid = (start+end) >> 1 ;
        return process(preSum , l , r , start , mid)
                + process(preSum , l , r , mid + 1 , end)
                + merge(preSum , l , r , start , mid , end);
    }
    public static int merge(int[] preSum , int l , int r , int start , int mid , int end){
        int i = start ;
        int j = mid + 1 ;
        int ans = 0 ;
        int[] merge = new int[end - start + 1];
        int m = 0 ;
        int winR = 0 ;
        int winL = 0 ;
        int rangeR = start ;
        int rangeL = start ;
        for(int a = mid + 1 ; a <= end ; a++){
            winR = preSum[a] - l ;
            winL = preSum[a] - r ;
            while(rangeR <= mid && preSum[rangeR] <= winR){
                rangeR++;
            }
            while(rangeL <= mid && preSum[rangeL] < winL){
                rangeL++;
            }
            ans += Math.max(0 , rangeR - rangeL);
        }
        while(i <= mid && j <= end){
            merge[m++] = preSum[i] < preSum[j]? preSum[i++]:preSum[j++];
        }
        while(i <= mid ){
            merge[m++] = preSum[i++];
        }
        while(j <= end){
            merge[m++] = preSum[j++];
        }
        for(int w = 0 ; w < merge.length ; w++){
            preSum[start + w] = merge[w];
        }
        return ans;
    }

    public static void main(String[] args){
//        int[] array = {12, 11 , -9 , 11 , 87};
        int[] array = {38, 95, 55, 79, 54, 45, 0, 25};
        // 一个：95
        // 二个：
        // 三个：95 + 0
        int l = 84 ;
        int r = 99;
//        ans1:1 , ans2:3 , l:84 , r:99
//        array:[38, 95, 55, 79, 54, 45, 0, 25]
        System.out.println(countRange(array , l , r));
        System.out.println(countRange(new int[]{32} , l , r));
        System.out.println(NumberComparator.countRange(array , l , r));
        System.out.println(countRange(null , l , r));
    }
}
